
//合并两个有序链表
 class ListNode {
      int val;
      ListNode next;
     ListNode() {}
      ListNode(int val) { this.val = val; }
     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  }

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {

        //创建一个虚拟结点(从此结点开始从list1和list2一个一个添加结点)
        ListNode newh = new ListNode(-1);

        //创建一个临时结点给newh添加结点
        ListNode tmp=newh;

        //每次只添加一个结点,小的一方的头结点移到下一位，大的一方不用移,每次都进行一次比较
        while(list1!=null&&list2!=null){
            if(list1.val>=list2.val){
                tmp.next=list2;
                list2=list2.next;
                // tmp=tmp.next;
            }else{
                tmp.next=list1;
                list1=list1.next;
                // tmp=tmp.next;
            }

            //tmp总是跟在新链表newh的表尾
            tmp=tmp.next;
        }

        //如果一方为空了，则另外一方肯定至少有一个结点没有连在新链表newh上面，不管剩余多少个结点都直接在新链的表尾接上即可
        if(list2==null){
            tmp.next=list1;
        }
        if(list1==null){
            tmp.next=list2;
        }

        return newh.next;
    }
}